package puzzle.projecteuler.p300;

import astudy.util.AdvMath;


public class Problem211B {

	/**
	 * @param args
	 */
	public static void main(String[] args) {

		
		int m = 64000000;
		
		long s = System.currentTimeMillis();
		long[] t = σ2(m);
		long sum = 0;
		int count = 0;
		for (int i = 1; i < t.length; i ++) {
			if (t[i] < 0) {
				System.out.println(i + "\t" + t[i]);
			}
			if (isSquare(t[i])) {
				sum += i;
				count ++;
//				System.out.println(i + "\t" + t[i] + "=" + Math.sqrt(t[i]) + "^2");
			}
		}
		System.out.println("count = " + count);
		System.out.println("sum = " + sum);
		System.out.println((System.currentTimeMillis()-s) + " ms");
	}
	
	private static boolean isSquare(long m) {
		if (m < 0) {
			return false;
		} else {
			long s = (long)Math.sqrt(m);
			return s*s == m;
		}
	}
	
	/**
	 * 采用类似筛法的方式，计算所有n(<m)对应的σ2(n)
	 * @param m
	 * @return
	 */
	public static long[] σ2(int m) {
		
		int sqrt_m = (int)Math.sqrt(m)+1;
		Integer[] primes = AdvMath.primes(sqrt_m);
		
		int[] tmp = new int[m+1];
		long[] res = new long[m+1];
		for (int i = 0; i < tmp.length; i ++) {
			tmp[i] = i;
			res[i] = 1;
		}
		
		tmp[0] = -1;
		res[0] = -1;
		tmp[1] = 1;
		res[1] = 1;
		
		for (int i = 0; i < primes.length; i ++) {
			long p = primes[i];
			for (int j = (int)p; j <= m; j += p) {
				int c = 0;
				while (tmp[j]%p == 0) {
					tmp[j] /= p;
					c ++;
				}
				res[j] *= (long)(Math.pow(p, 2*c+2)-1)/(long)(Math.pow(p, 2)-1);
			}
		}
		for (int i = 1; i < tmp.length; i ++) {
			if (tmp[i] != 1) {
				res[i] *= (long)tmp[i]*tmp[i]+1; 
			}
		}

		return res;
	} 
}
